Data may be transmitted according to one of many data transfer protocols. Data transfer protocols generally include protocols defined by industry standards bodies or proprietary protocols. While different protocols may have advantages and disadvantages, a data transmission protocol may be selected to optimize the transmission of data according to the application using the protocol. Various digital communications standards such as IEEE 802.11, IEEE 802.16, or Digital Video Broadcasting-Terrestrial (DVB-T) use Fourier Transforms, and in particular use Fourier Transforms as part of Orthogonal Frequency Division Multiplexing (OFDM) systems. Various implementations of Fourier transforms are provided in a set of algorithms called Fast Fourier Transforms (FFT). The inverse operation of a Fast Fourier Transform is called Inverse Fast Fourier Transform (IFFT). FFT algorithms may be implemented using Radix-2, Radix-4, or some other Radix algorithm.
In uniform implementations of forward FFT or inverse FFT, if the input data to the FFT algorithm is provided from a bit or digit reversed address index (as is the case with decimation in time FFT algorithm, for example), then the output data of FFT is in a natural order address indexing order. Similarly if the input is in a natural order (as is the case with decimation in frequency FFT algorithm, for example), the output of FFT is in a bit or digit reversed order. Bit reversed order is based on binary number representation of the index. A 16 point FFT block has 16 data values represented by an index of 0, 1, 2, 3 . . . , 14, 15. These 16 index values are represented in binary as 0000, 0001, 0010, . . . , 1110, 1111, as is well known. A corresponding bit reversed index is generated by reversing the order of the binary bits to represent the bit reversed index. Accordingly, the natural index as previously shown corresponds to a bit reversed order of 0000, 1000, 0100, . . . , 0111, 1111. That is, the binary value 0001 corresponding to the decimal value of “1” will be represented in bit-reversed order as a binary value of 1000. Similarly, the binary value 0010 corresponding to the decimal value of “2” will be represented in bit reversed order as a binary value of 0100. Therefore, the sequence of consecutive decimal integers from 0-15 translates to the decimal values 0, 8, 4, . . . 7, 15 in bit reversed order. Accordingly, for a given order of indexing of FFT input data, the output data of the FFT will be in a modified indexing order for that 16 value block. For Radix-2 algorithms, bit reversed ordering is possible. However, it is possible to reverse and shift group of bits in the memory address generation logic to be able to support other radices. For higher radix implementations, digit reversed ordering is used. Digit reversed order is another form of a modified address order, where instead of a group of 1 bit, it has a group of 2 or more bits which are reversed. Because Radix-4 will have a 4 digit value grouping (0, 1, 2, 3), the reversed ordering is in groups of 2 bits. Similarly, the reversed ordering in Radix-8 will be in group of 3 bits.
In any application requiring bit or digit reversion, bit-reversed to natural conversion or natural to bit reversed conversion is needed at either the input or at the output. For an N point FFT circuit, N values of data have to be stored to convert from natural to bit reversed order, typically at the FFT circuit's input. If the FFT circuit operates in burst mode, for example in a loop engine implementation, then the FFT circuit will generate the 1024 value results. The natural to bit reversed order conversion will start, and once the conversion is completed, the FFT circuit will process the next block of data. However, an FFT circuit needs to read the data from a buffer space which does not interfere with the natural to bit reversed order conversion. Conventional circuits implementing an FFT circuit have used double buffering, commonly called ping pong buffering. As shown for example in FIG. 1, an FFT circuit 102 is coupled by a multiplexer 104 to receive the output of a first buffer circuit 106. The buffer circuit 106 comprises a buffer 108 coupled to receive an address at the output of a multiplexer 110, which is coupled to receive a read address from a read address circuit 112 and a write address from a write address circuit 114. Similarly, a buffer circuit 116 comprises a buffer 118 coupled to receive the output of a multiplexer 120, which is coupled to receive either a read address from a read address circuit 122 and a write address from a write address circuit 124.
A write enable signal coupled to an inverter 126 is used to select whether a read address or write address is coupled to the buffers, which are also enabled by the write enable signal. The read address circuits 112 and 122 are controlled by the FFT circuit 102. As can be seen in the conventional circuit of FIG. 1, two buffers are required, where each buffer receives a separate read or write address. Accordingly, while a first buffer circuit is storing data in a first order, such as a natural order, the FFT circuit accesses the second buffer circuit which enables a natural-to-bit reversed conversion of the data stored in the buffer by allowing the data to be read in the bit reversed order. After the data is read from the second buffer circuit, the FFT circuit will then switch and a natural-to-bit reversed conversion of the data stored in the first buffer circuit by allowing that data to be read in the bit reversed order.
However, the circuit of FIG. 1 is an inefficient use of resources. For example, the dual buffer requirement and additional logic to control both read and write addresses to both buffers increases the circuit requirement to implement the FFT circuit. Such additional circuitry can be particularly costly in certain circuits where resources must be used efficiently. For example, in a programmable logic device where the efficient use of available logic resources is important, the additional circuitry is particularly inefficient.
Accordingly, there is a need for an improved method of and circuit for buffering data.